package com.example.demo.leetcode.classics150;

import java.util.*;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _122IPO
 * @description
 * @date 2023/08/17 20:35
 * <p>
 * ******************************************************
 */
public class _122IPO {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(new int[]{capital[i], profits[i]});
        }
        list.sort(Comparator.comparingInt(a -> a[0]));
        PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> b - a);

        // 第一批：将不大于w的项目加入队列中，拿出最大的利润，更新w
        // 第二批：将不大于w+第一个项目的利润的项目加入队列中，拿出最大的利润，更新w
        // ...........直到拿到第k项目，结束
        int i = 0;
        while (k-- > 0) {
            while (i < n && list.get(i)[0] <= w) q.add(list.get(i++)[1]);
            if (q.isEmpty()) break;
            w += q.poll();
        }
        return w;
    }
}
